package algorithm.dynamic_programming;


public class HorseJump {

    public static int jump(int a, int b, int k){
        if(a > 9 || b > 8)
            return 0;
        return process(a, b, 0, 0, k);
    }

    public static int process(int a, int b, int x, int y, int rest){
        if(x > 9 || y > 8 || x < 0 || y < 0)
            return 0;
        if(rest == 0)
            return x == a && y == b? 1 : 0;
        int num = process(a, b, x - 2, y + 1, rest - 1);
        num += process(a, b, x - 1, y + 2, rest - 1);
        num += process(a, b, x + 1, y + 2, rest - 1);
        num += process(a, b, x + 2, y + 1, rest - 1);
        num += process(a, b, x + 2, y - 1, rest - 1);
        num += process(a, b, x + 1, y - 2, rest - 1);
        num += process(a, b, x - 1, y - 2, rest - 1);
        num += process(a, b, x - 2, y - 1, rest - 1);
        return num;
    }

    public static int jump2(int a, int b, int k){
        if(a > 9 || b > 8)
            return 0;
        int[][][] dp = new int[10][9][k + 1];
        dp[a][b][0] = 1;
        for (int rest = 1; rest < k + 1; rest++) {
            for (int x = 0; x < 10; x++) {
                for (int y = 0; y < 9; y++) {
                    dp[x][y][rest] = pick(x - 2, y + 1, rest - 1, dp) +
                            pick(x - 1, y + 2, rest - 1, dp) +
                            pick(x + 1, y + 2, rest - 1, dp) +
                            pick(x + 2, y + 1, rest - 1, dp) +
                            pick(x + 2, y - 1, rest - 1, dp) +
                            pick(x + 1, y - 2, rest - 1, dp) +
                            pick(x - 1, y - 2, rest - 1, dp) +
                            pick(x - 2, y - 1, rest - 1, dp);
                }
            }
        }
        return dp[0][0][k];
    }

    public static int pick(int x, int y, int rest, int[][][] dp){
        if(x < 0 || y < 0 || x > 9 || y > 8)
            return 0;
        else
            return dp[x][y][rest];
    }

    public static void main(String[] args) {
        int x = 7;
        int y = 7;
        int step = 10;
        System.out.println(jump2(x, y, step));

        System.out.println(jump(x, y, step));
    }
}
